18870번 좌표 압축

Day16 13단계 20231110

• 계속해서 시간 초과가 떠서 다른 사람의 풀이를 참고했다. https://st-lab.tistory.com/279
• 내 풀이 시도 : 입력 받은 값을 저장한 배열을 생성하고, 이 배열을 정렬한 다른 배열을 생성한다.
  • 원본 배열의 첫 요소부터 마지막까지 새로 정렬된 배열의 요소와 비교해서 크기가 크고 중복되지 않은 경우에만 count++를 수행했다.
  • 중복 제거를 위해 HashMap을 사용했었는데도 시간 초과가 떴다.
• 다른 사람 풀이를 참고해보니 배열 요소의 크기에 따른 우선순위를 부여하는 방법에 대한 설명이 있어 이 부분을 생각해서 코드를 수정했다.

• 문제에서 주어진 값의 범위를 잘 살펴보자.. 계산 실수로 인해 int로 풀 수 있는 것을 Long으로 풀어서 더 오래 걸렸다.
• Long을 썼을 때는 TreeSet을 사용한 정렬 및 중복 제거가 빨랐지만, int와 Integer로 변경하니 int 배열을 복사해서 Arrays.sort()것보다 좀 더 느렸다.
  • Long, Integer와 같은 Wrapper 클래스 저장 위치와 기본 자료형 저장 위치가 달라서 값을 처리하는 과정에서 발생한 차이로 보인다.

1. 처음 시도한 코드

• 이 코드는 시간 초과가 뜬 코드다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String[] nums = br.readLine().split(" ");
        Long[] arr = new Long[n];
        for (int i = 0; i < n; i++) {
        	arr[i] = Long.parseLong(nums[i]);
        }
		Arrays.sort(arr);
		
		StringBuilder sb = new StringBuilder();
		int count = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n - 1; j++) {
				if (Long.parseLong(nums[i]) > arr[j] && !arr[j].equals(arr[j+1])) {
					count++;
				}
			}
			sb.append(count+" ");
			count = 0;
		}

		System.out.println(sb.toString());
		br.close();
	}
}

2. 1차 수정 코드

• 이 코드는 다른 사람의 풀이를 참고해서 수정한 코드다.
• 이 코드의 처리 시간은 3004 ms(!)이다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
        // reference : https://st-lab.tistory.com/279
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		Long[] arr = new Long[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}
		Long[] arr2 = Arrays.copyOf(arr, arr.length);
		Arrays.sort(arr2);
		
		Map<Long, Integer> map = new HashMap<>();
		int rank = 0;
		for (int i = 0; i < n; i++) {
			if (!map.containsKey(arr2[i]))
				map.put(arr2[i], rank++);
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			sb.append(map.get(arr[i])+" ");
		}

		System.out.println(sb.toString());
		br.close();
	}
}

3. 2차 수정 코드

• 위 코드에서 arr2를 Arrays.copyOf()가 아닌 arr 배열을 채울 때 같이 채우는 방법으로 바꿔봤다.
• 이 코드의 처리 시간은 3096 ms으로, 위의 코드보다 시간이 더 걸렸다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
        // reference : https://st-lab.tistory.com/279
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		Long[] arr = new Long[n];
		Long[] arr2 = new Long[n]; // 1차 수정 비교
		for (int i = 0; i < n; i++) {
			arr[i] = arr2[i] = Long.parseLong(st.nextToken()); // 1차 수정 비교
		}
		Arrays.sort(arr2);
		
		Map<Long, Integer> map = new HashMap<>();
		int rank = 0;
		for (int i = 0; i < n; i++) {
			if (!map.containsKey(arr2[i]))
				map.put(arr2[i], rank++);
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			sb.append(map.get(arr[i])+" ");
		}

		System.out.println(sb.toString());
		br.close();
	}
}

4. 3차 수정 코드

• 위의 결과들이 속도가 느려서 챗gpt에 수정을 요청한 결과를 가져왔다.
• 정렬을 위한 arr2라는 배열을 새로 만들어서 정렬하는 대신 TreeSet을 사용해서 자동 정렬 및 중복 제거를 수행한다.
• 이 코드는 처리 시간이 2292 ms(!)로, 위의 코드들보다 많이 빨라졌다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // reference : https://st-lab.tistory.com/279
        // 챗gpt로 이전 코드를 수정한 결과 테스트
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Long[] arr = new Long[n];

        TreeSet<Long> set = new TreeSet<>(); // 2차 수정(챗gpt)
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(st.nextToken());
            set.add(arr[i]); // 2차 수정(챗gpt)
        }

        Map<Long, Integer> map = new HashMap<>();
        int rank = 0;
        for (long value : set) { // 2차 수정(챗gpt)
            map.put(value, rank++);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(map.get(arr[i])).append(" "); // 2차 수정(챗gpt)
        }

        System.out.println(sb.toString());
        br.close();
    }
}

5. 4차 수정 코드

• 위의 3차 수정 코드에서 다른 사람들의 코드와 비교하던 중 자료형이 모두 int인 것을 발견했다.
• 문제에서 값의 범위가 -10^9 <= x <= 10^9인 것을 잘못 계산하여 Long형으로 작성해서 실제 int형으로 바꾸면 속도가 올라가는지 비교했다.
• 이 코드의 처리 시간은 2020 ms으로, 3차 코드보다 속도가 빠르다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // referecne : https://st-lab.tistory.com/279
        // 챗gpt로 이전 코드를 수정한 결과 테스트
        // 자료형을 Long -> int로 바꿈
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int[] arr = new int[n]; // 3차 수정 테스트

        TreeSet<Integer> set = new TreeSet<>(); // 3차 수정 테스트

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken()); // 3차 수정 테스트
            set.add(arr[i]);
        }

        Map<Integer, Integer> map = new HashMap<>(); // 3차 수정 테스트
        int rank = 0;

        for (int i : set) { // 3차 수정 테스트
            map.put(i, rank++);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(map.get(arr[i])).append(" ");
        }

        System.out.println(sb.toString());
        br.close();
    }
}

6. 5차 수정 코드

• 다른 사람들의 풀이와 비교하던 중 1차 및 2차 코드의 형태와 동일하고 자료형만 다른데 속도가 많이 빨라서 테스트해보았다.
• 이 코드의 처리 시간은 2032 ms 로, Long형을 사용했던 코드의 처리 시간인 3004 ms보다 빠르다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
        // reference : https://st-lab.tistory.com/279
		// 69101244 제출에서 자료형을 Long -> int로 바꿈
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int[] arr2 = Arrays.copyOf(arr, arr.length);
		Arrays.sort(arr2);
		
		Map<Integer, Integer> map = new HashMap<>();
		int rank = 0;
		for (int i = 0; i < n; i++) {
			if (!map.containsKey(arr2[i]))
				map.put(arr2[i], rank++);
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			sb.append(map.get(arr[i])+" ");
		}

		System.out.println(sb.toString());
		br.close();
	}
}